/**
 * 
 */
package sort;

import java.util.Comparator;
import java.util.List;

/**
 * @author Thomas Xu
 *
 */
public class MergeSort<T> {
	
	private Comparator<T> _comp;
	private boolean _order;
	
	public MergeSort(Comparator<T> comp){

		this._comp = comp;
	}
	
	public void sort(T[] arr, T[] temp, boolean asc){
		this._order = asc;
		mergeSort (arr, 0, arr.length, temp);
	}
	
	private void mergeSort(T[] a, int from, int to, T[] b){
		if( to - from < 2) return;
		
		int mid = (from + to)/2;
		mergeSort(a, from, mid, b);
		mergeSort(a, mid, to, b);
		doMerge(a, from, mid, to, b);
		copyArray(b, from, to, a);
	}
	
	private void doMerge(T[] a, int from, int mid, int to, T[] b){
		int i0 = from, i1 = mid;
		
		for(int j = from; j< to; j++){
			if( i0 < mid && ( i1 >= to || compare(a[i0], b[i1]))){
				b[j] = a[i0];
				i0++;
			}else{
				b[j] = a[i1];
				i1 ++;
			}
		}
	}
	
	private boolean compare (T a, T b){
		if(_order) return _comp.compare(a, b) <=0;
		else return _comp.compare(a, b) >=0;
	}
	
	private void copyArray(T[] b, int from, int to , T[] a){
		for( int i = from; i < to ; i++){
			a[i] = b[i];
		}
	}

}
